import MockTerrainProvider from '../MockTerrainProvider.js';
import TerrainTileProcessor from '../TerrainTileProcessor.js';
import { Cartesian3 } from '../../Source/Cesium.js';
import { Cartographic } from '../../Source/Cesium.js';
import { defined } from '../../Source/Cesium.js';
import { defineProperties } from '../../Source/Cesium.js';
import { Ellipsoid } from '../../Source/Cesium.js';
import { EventHelper } from '../../Source/Cesium.js';
import { GeographicProjection } from '../../Source/Cesium.js';
import { GeographicTilingScheme } from '../../Source/Cesium.js';
import { Intersect } from '../../Source/Cesium.js';
import { Rectangle } from '../../Source/Cesium.js';
import { Visibility } from '../../Source/Cesium.js';
import { Camera } from '../../Source/Cesium.js';
import { GlobeSurfaceTileProvider } from '../../Source/Cesium.js';
import { ImageryLayerCollection } from '../../Source/Cesium.js';
import { QuadtreePrimitive } from '../../Source/Cesium.js';
import { QuadtreeTileLoadState } from '../../Source/Cesium.js';
import { SceneMode } from '../../Source/Cesium.js';
import createScene from '../createScene.js';
import pollToPromise from '../pollToPromise.js';
import { when } from '../../Source/Cesium.js';

describe('Scene/QuadtreePrimitive', function() {

    describe('selectTilesForRendering', function() {
        var scene;
        var camera;
        var frameState;
        var quadtree;
        var mockTerrain;
        var tileProvider;
        var imageryLayerCollection;
        var surfaceShaderSet;
        var processor;
        var rootTiles;

        beforeEach(function() {
            scene = {
                mapProjection: new GeographicProjection(),
                drawingBufferWidth: 1000,
                drawingBufferHeight: 1000
            };

            camera = new Camera(scene);

            frameState = {
                frameNumber: 0,
                passes: {
                    render: true
                },
                camera: camera,
                fog: {
                    enabled: false
                },
                context: {
                    drawingBufferWidth: scene.drawingBufferWidth,
                    drawingBufferHeight: scene.drawingBufferHeight
                },
                mode: SceneMode.SCENE3D,
                commandList: [],
                cullingVolume: jasmine.createSpyObj('CullingVolume', ['computeVisibility']),
                afterRender: [],
                pixelRatio: 1.0
            };

            frameState.cullingVolume.computeVisibility.and.returnValue(Intersect.INTERSECTING);

            imageryLayerCollection = new ImageryLayerCollection();
            surfaceShaderSet = jasmine.createSpyObj('SurfaceShaderSet', ['getShaderProgram']);
            mockTerrain = new MockTerrainProvider();
            tileProvider = new GlobeSurfaceTileProvider({
                terrainProvider: mockTerrain,
                imageryLayers: imageryLayerCollection,
                surfaceShaderSet: surfaceShaderSet
            });
            quadtree = new QuadtreePrimitive({
                tileProvider: tileProvider
            });

            processor = new TerrainTileProcessor(frameState, mockTerrain, imageryLayerCollection);

            quadtree.render(frameState);
            rootTiles = quadtree._levelZeroTiles;

            processor.mockWebGL();
        });

        function process(quadtreePrimitive, callback) {
            var deferred = when.defer();

            function next() {
                ++frameState.frameNumber;
                quadtree.beginFrame(frameState);
                quadtree.render(frameState);
                quadtree.endFrame(frameState);

                if (callback()) {
                    setTimeout(next, 0);
                } else {
                    deferred.resolve();
                }
            }

            next();

            return deferred.promise;
        }

        it('must be constructed with a tileProvider', function() {
            expect(function() {
                return new QuadtreePrimitive();
            }).toThrowDeveloperError();

            expect(function() {
                return new QuadtreePrimitive({});
            }).toThrowDeveloperError();
        });

        it('selects nothing when the root tiles are not yet ready', function() {
            quadtree.render(frameState);
            expect(quadtree._tilesToRender.length).toBe(0);
        });

        it('selects root tiles once they are ready', function() {
            mockTerrain
                .requestTileGeometryWillSucceed(rootTiles[0])
                .requestTileGeometryWillSucceed(rootTiles[1])
                .createMeshWillSucceed(rootTiles[0])
                .createMeshWillSucceed(rootTiles[1]);

            return processor.process(rootTiles).then(function() {
                quadtree.render(frameState);

                // There should be at least one selected tile.
                expect(quadtree._tilesToRender.length).toBeGreaterThan(0);

                // All selected tiles should be root tiles.
                expect(quadtree._tilesToRender.filter(function(tile) { return tile.level === 0; }).length).toBe(quadtree._tilesToRender.length);
            });
        });

        it('selects deeper tiles once they are renderable', function() {
            mockTerrain
                .requestTileGeometryWillSucceed(rootTiles[0])
                .requestTileGeometryWillSucceed(rootTiles[1])
                .createMeshWillSucceed(rootTiles[0])
                .createMeshWillSucceed(rootTiles[1]);

            rootTiles[0].children.forEach(function(tile) {
                mockTerrain
                    .requestTileGeometryWillSucceed(tile)
                    .createMeshWillSucceed(tile);
                expect(tile.renderable).toBe(false);
            });

            return processor.process(rootTiles).then(function() {
                quadtree.render(frameState);

                // All selected tiles should be root tiles.
                expect(quadtree._tilesToRender.length).toBeGreaterThan(0);
                expect(quadtree._tilesToRender.filter(function(tile) { return tile.level === 0; }).length).toBe(quadtree._tilesToRender.length);

                // Allow the child tiles to load.
                return processor.process(rootTiles[0].children);
            }).then(function() {
                quadtree.render(frameState);

                // Now child tiles should be rendered too.
                expect(quadtree._tilesToRender).toContain(rootTiles[0].southwestChild);
                expect(quadtree._tilesToRender).toContain(rootTiles[0].southeastChild);
                expect(quadtree._tilesToRender).toContain(rootTiles[0].northwestChild);
                expect(quadtree._tilesToRender).toContain(rootTiles[0].northeastChild);
            });
        });

        it('skips loading levels when tiles are known to be available', function() {
            // Mark all tiles through level 2 as available.
            rootTiles.forEach(function(tile) {
                // level 0 tile
                mockTerrain
                    .willBeAvailable(tile)
                    .requestTileGeometryWillSucceed(tile)
                    .createMeshWillSucceed(tile);

                tile.children.forEach(function(tile) {
                    // level 1 tile
                    mockTerrain
                        .willBeAvailable(tile)
                        .requestTileGeometryWillSucceed(tile)
                        .createMeshWillSucceed(tile);

                    tile.children.forEach(function(tile) {
                        // level 2 tile
                        mockTerrain
                            .willBeAvailable(tile)
                            .requestTileGeometryWillSucceed(tile)
                            .createMeshWillSucceed(tile);
                    });
                });
            });

            quadtree.preloadAncestors = false;

            // Look down at the center of a level 2 tile from a distance that will refine to it.
            var lookAtTile = rootTiles[0].southwestChild.northeastChild;
            setCameraPosition(quadtree, frameState, Rectangle.center(lookAtTile.rectangle), lookAtTile.level);

            spyOn(mockTerrain, 'requestTileGeometry').and.callThrough();

            return process(quadtree, function() {
                // Process until the lookAtTile is rendered. That tile's parent (level 1)
                // should not be rendered along the way.
                expect(quadtree._tilesToRender).not.toContain(lookAtTile.parent);
                var lookAtTileRendered = quadtree._tilesToRender.indexOf(lookAtTile) >= 0;
                var continueProcessing = !lookAtTileRendered;
                return continueProcessing;
            }).then(function() {
                // The lookAtTile should be a real tile, not a fill.
                expect(quadtree._tilesToRender).toContain(lookAtTile);
                expect(lookAtTile.data.fill).toBeUndefined();
                expect(lookAtTile.data.vertexArray).toBeDefined();

                // The parent of the lookAtTile should not have been requested.
                var parent = lookAtTile.parent;
                mockTerrain.requestTileGeometry.calls.allArgs().forEach(function(call) {
                    expect(call.slice(0, 3)).not.toEqual([parent.x, parent.y, parent.level]);
                });
            });
        });

        it('does not skip loading levels if availability is unknown', function() {
            // Mark all tiles through level 2 as available.
            rootTiles.forEach(function(tile) {
                // level 0 tile
                mockTerrain
                    .requestTileGeometryWillSucceed(tile)
                    .createMeshWillSucceed(tile);

                tile.children.forEach(function(tile) {
                    // level 1 tile
                    mockTerrain
                        .willBeAvailable(tile)
                        .requestTileGeometryWillSucceed(tile)
                        .createMeshWillSucceed(tile);

                    tile.children.forEach(function(tile) {
                        // level 2 tile
                        mockTerrain
                            .willBeUnknownAvailability(tile)
                            .requestTileGeometryWillSucceed(tile)
                            .createMeshWillSucceed(tile);
                    });
                });
            });

            quadtree.preloadAncestors = false;

            // Look down at the center of a level 2 tile from a distance that will refine to it.
            var lookAtTile = rootTiles[0].southwestChild.northeastChild;
            setCameraPosition(quadtree, frameState, Rectangle.center(lookAtTile.rectangle), lookAtTile.level);

            spyOn(mockTerrain, 'requestTileGeometry').and.callThrough();

            return process(quadtree, function() {
                // Process until the lookAtTile is rendered. That tile's parent (level 1)
                // should not be rendered along the way, but it will be loaded.
                expect(quadtree._tilesToRender).not.toContain(lookAtTile.parent);
                var lookAtTileRendered = quadtree._tilesToRender.indexOf(lookAtTile) >= 0;
                var continueProcessing = !lookAtTileRendered;
                return continueProcessing;
            }).then(function() {
                // The lookAtTile should be a real tile, not a fill.
                expect(quadtree._tilesToRender).toContain(lookAtTile);
                expect(lookAtTile.data.fill).toBeUndefined();
                expect(lookAtTile.data.vertexArray).toBeDefined();

                // The parent of the lookAtTile should have been requested before the lookAtTile itself.
                var parent = lookAtTile.parent;
                var allArgs = mockTerrain.requestTileGeometry.calls.allArgs();
                var parentArgsIndex = allArgs.indexOf(allArgs.filter(function(call) {
                    return call[0] === parent.x && call[1] === parent.y && call[2] === parent.level;
                })[0]);
                var lookAtArgsIndex = allArgs.indexOf(allArgs.filter(function(call) {
                    return call[0] === lookAtTile.x && call[1] === lookAtTile.y && call[2] === lookAtTile.level;
                })[0]);
                expect(parentArgsIndex).toBeLessThan(lookAtArgsIndex);
            });
        });

        it('loads and renders intermediate tiles according to loadingDescendantLimit', function() {
            // Mark all tiles through level 2 as available.
            rootTiles.forEach(function(tile) {
                // level 0 tile
                mockTerrain
                    .willBeAvailable(tile)
                    .requestTileGeometryWillSucceed(tile)
                    .createMeshWillSucceed(tile);

                tile.children.forEach(function(tile) {
                    // level 1 tile
                    mockTerrain
                        .willBeAvailable(tile)
                        .requestTileGeometryWillSucceed(tile)
                        .createMeshWillSucceed(tile);

                    tile.children.forEach(function(tile) {
                        // level 2 tile
                        mockTerrain
                            .willBeAvailable(tile)
                            .requestTileGeometryWillSucceed(tile)
                            .createMeshWillSucceed(tile);
                    });
                });
            });

            quadtree.preloadAncestors = false;
            quadtree.loadingDescendantLimit = 1;

            // Look down at the center of a level 2 tile from a distance that will refine to it.
            var lookAtTile = rootTiles[0].southwestChild.northeastChild;
            setCameraPosition(quadtree, frameState, Rectangle.center(lookAtTile.rectangle), lookAtTile.level);

            spyOn(mockTerrain, 'requestTileGeometry').and.callThrough();

            return process(quadtree, function() {
                // First the lookAtTile's parent should be rendered.
                var lookAtTileParentRendered = quadtree._tilesToRender.indexOf(lookAtTile.parent) >= 0;
                var continueProcessing = !lookAtTileParentRendered;
                return continueProcessing;
            }).then(function() {
                // The lookAtTile's parent should be a real tile, not a fill.
                expect(quadtree._tilesToRender).toContain(lookAtTile.parent);
                expect(lookAtTile.parent.data.fill).toBeUndefined();
                expect(lookAtTile.parent.data.vertexArray).toBeDefined();

                return process(quadtree, function() {
                    // Then the lookAtTile should be rendered.
                    var lookAtTileRendered = quadtree._tilesToRender.indexOf(lookAtTile) >= 0;
                    var continueProcessing = !lookAtTileRendered;
                    return continueProcessing;
                });
            }).then(function() {
                // The lookAtTile should be a real tile, not a fill.
                expect(quadtree._tilesToRender).toContain(lookAtTile);
                expect(lookAtTile.data.fill).toBeUndefined();
                expect(lookAtTile.data.vertexArray).toBeDefined();
            });
        });

        it('continues rendering more detailed tiles when camera zooms out and an appropriate ancestor is not yet renderable', function() {
            // Mark all tiles through level 2 as available.
            rootTiles.forEach(function(tile) {
                // level 0 tile
                mockTerrain
                    .willBeAvailable(tile)
                    .requestTileGeometryWillSucceed(tile)
                    .createMeshWillSucceed(tile);

                tile.children.forEach(function(tile) {
                    // level 1 tile
                    mockTerrain
                        .willBeAvailable(tile)
                        .requestTileGeometryWillSucceed(tile)
                        .createMeshWillSucceed(tile);

                    tile.children.forEach(function(tile) {
                        // level 2 tile
                        mockTerrain
                            .willBeAvailable(tile)
                            .requestTileGeometryWillSucceed(tile)
                            .createMeshWillSucceed(tile);
                    });
                });
            });

            quadtree.preloadAncestors = false;

            // Look down at the center of a level 2 tile from a distance that will refine to it.
            var lookAtTile = rootTiles[0].southwestChild.northeastChild;
            setCameraPosition(quadtree, frameState, Rectangle.center(lookAtTile.rectangle), lookAtTile.level);

            spyOn(mockTerrain, 'requestTileGeometry').and.callThrough();

            return process(quadtree, function() {
                // Process until the lookAtTile is rendered. That tile's parent (level 1)
                // should not be rendered along the way.
                expect(quadtree._tilesToRender).not.toContain(lookAtTile.parent);
                var lookAtTileRendered = quadtree._tilesToRender.indexOf(lookAtTile) >= 0;
                var continueProcessing = !lookAtTileRendered;
                return continueProcessing;
            }).then(function() {
                // Zoom out so the parent tile no longer needs to refine to meet SSE.
                setCameraPosition(quadtree, frameState, Rectangle.center(lookAtTile.rectangle), lookAtTile.parent.level);

                // Select new tiles
                quadtree.beginFrame(frameState);
                quadtree.render(frameState);
                quadtree.endFrame(frameState);

                // The lookAtTile should still be rendered, not it's parent.
                expect(quadtree._tilesToRender).toContain(lookAtTile);
                expect(quadtree._tilesToRender).not.toContain(lookAtTile.parent);

                return process(quadtree, function() {
                    // Eventually the parent should be rendered instead.
                    var parentRendered = quadtree._tilesToRender.indexOf(lookAtTile.parent) >= 0;
                    var continueProcessing = !parentRendered;
                    return continueProcessing;
                });
            }).then(function() {
                expect(quadtree._tilesToRender).not.toContain(lookAtTile);
                expect(quadtree._tilesToRender).toContain(lookAtTile.parent);
            });
        });

        it('renders a fill for a newly-visible tile', function() {
            // Mark all tiles through level 2 as available.
            rootTiles.forEach(function(tile) {
                // level 0 tile
                mockTerrain
                    .willBeAvailable(tile)
                    .requestTileGeometryWillSucceed(tile)
                    .createMeshWillSucceed(tile);

                tile.children.forEach(function(tile) {
                    // level 1 tile
                    mockTerrain
                        .willBeAvailable(tile)
                        .requestTileGeometryWillSucceed(tile)
                        .createMeshWillSucceed(tile);

                    tile.children.forEach(function(tile) {
                        // level 2 tile
                        mockTerrain
                            .willBeAvailable(tile)
                            .requestTileGeometryWillSucceed(tile)
                            .createMeshWillSucceed(tile);
                    });
                });
            });

            quadtree.preloadAncestors = false;

            var visibleTile = rootTiles[0].southwestChild.northeastChild;
            var notVisibleTile = rootTiles[0].southwestChild.northwestChild;

            frameState.cullingVolume.computeVisibility.and.callFake(function(boundingVolume) {
                if (!defined(visibleTile.data)) {
                    return Intersect.INTERSECTING;
                }

                if (boundingVolume === visibleTile.data.orientedBoundingBox) {
                    return Intersect.INTERSECTING;
                } else if (boundingVolume === notVisibleTile.data.orientedBoundingBox) {
                    return Intersect.OUTSIDE;
                }
                return Intersect.INTERSECTING;
            });

            // Look down at the center of the visible tile.
            setCameraPosition(quadtree, frameState, Rectangle.center(visibleTile.rectangle), visibleTile.level);

            spyOn(mockTerrain, 'requestTileGeometry').and.callThrough();

            return process(quadtree, function() {
                // Process until the visibleTile is rendered.
                var visibleTileRendered = quadtree._tilesToRender.indexOf(visibleTile) >= 0;
                var continueProcessing = !visibleTileRendered;
                return continueProcessing;
            }).then(function() {
                expect(quadtree._tilesToRender).not.toContain(notVisibleTile);

                // Now treat the not-visible-tile as visible.
                frameState.cullingVolume.computeVisibility.and.returnValue(Intersect.INTERSECTING);

                // Select new tiles
                quadtree.beginFrame(frameState);
                quadtree.render(frameState);
                quadtree.endFrame(frameState);

                // The notVisibleTile should be rendered as a fill.
                expect(quadtree._tilesToRender).toContain(visibleTile);
                expect(quadtree._tilesToRender).toContain(notVisibleTile);
                expect(notVisibleTile.data.fill).toBeDefined();
                expect(notVisibleTile.data.vertexArray).toBeUndefined();
            });
        });
    });

    describe('with mock tile provider', function() {
        var scene;

        beforeAll(function() {
            scene = createScene();
            scene.render();
        });

        afterAll(function() {
            scene.destroyForSpecs();
        });

        function createSpyTileProvider() {
            var result = jasmine.createSpyObj('tileProvider', [
                'getQuadtree', 'setQuadtree', 'getReady', 'getTilingScheme', 'getErrorEvent',
                'initialize', 'updateImagery', 'beginUpdate', 'endUpdate', 'getLevelMaximumGeometricError', 'loadTile',
                'computeTileVisibility', 'showTileThisFrame', 'computeDistanceToTile', 'canRefine', 'isDestroyed', 'destroy']);

            defineProperties(result, {
                quadtree : {
                    get : result.getQuadtree,
                    set : result.setQuadtree
                },
                ready : {
                    get : result.getReady
                },
                tilingScheme : {
                    get : result.getTilingScheme
                },
                errorEvent : {
                    get : result.getErrorEvent
                }
            });

            var tilingScheme = new GeographicTilingScheme();
            result.getTilingScheme.and.returnValue(tilingScheme);

            result.canRefine.and.callFake(function(tile) {
                return tile.renderable;
            });

            return result;
        }

        it('calls initialize, beginUpdate, loadTile, and endUpdate', function() {
            var tileProvider = createSpyTileProvider();
            tileProvider.getReady.and.returnValue(true);

            var quadtree = new QuadtreePrimitive({
                tileProvider : tileProvider
            });

            // determine what tiles to load
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // load tiles
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            expect(tileProvider.initialize).toHaveBeenCalled();
            expect(tileProvider.beginUpdate).toHaveBeenCalled();
            expect(tileProvider.loadTile).toHaveBeenCalled();
            expect(tileProvider.endUpdate).toHaveBeenCalled();
        });

        it('shows the root tiles when they are ready and visible', function() {
            var tileProvider = createSpyTileProvider();
            tileProvider.getReady.and.returnValue(true);
            tileProvider.computeTileVisibility.and.returnValue(Visibility.FULL);
            tileProvider.loadTile.and.callFake(function(frameState, tile) {
                tile.renderable = true;
            });

            var quadtree = new QuadtreePrimitive({
                tileProvider : tileProvider
            });

            // determine what tiles to load
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // load tiles
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            expect(tileProvider.showTileThisFrame).toHaveBeenCalled();
        });

        it('stops loading a tile that moves to the DONE state', function() {
            var tileProvider = createSpyTileProvider();
            tileProvider.getReady.and.returnValue(true);
            tileProvider.computeTileVisibility.and.returnValue(Visibility.FULL);

            var calls = 0;
            tileProvider.loadTile.and.callFake(function(frameState, tile) {
                ++calls;
                tile.state = QuadtreeTileLoadState.DONE;
            });

            var quadtree = new QuadtreePrimitive({
                tileProvider : tileProvider
            });

            // determine what tiles to load
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // load tiles
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            expect(calls).toBe(2);

            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            expect(calls).toBe(2);
        });

        it('tileLoadProgressEvent is raised when tile loaded and when new children discovered', function() {
            var eventHelper = new EventHelper();

            var tileProvider = createSpyTileProvider();
            tileProvider.getReady.and.returnValue(true);
            tileProvider.computeTileVisibility.and.returnValue(Visibility.FULL);

            var quadtree = new QuadtreePrimitive({
                tileProvider : tileProvider
            });

            var progressEventSpy = jasmine.createSpy('progressEventSpy');
            eventHelper.add(quadtree.tileLoadProgressEvent, progressEventSpy);

            // Initial update to get the zero-level tiles set up.
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // load zero-level tiles
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            quadtree.update(scene.frameState);

            scene.renderForSpecs();

            // There will now be two zero-level tiles in the load queue.
            expect(progressEventSpy.calls.mostRecent().args[0]).toEqual(2);

            // Change one to loaded and update again
            quadtree._levelZeroTiles[0].state = QuadtreeTileLoadState.DONE;
            quadtree._levelZeroTiles[1].state = QuadtreeTileLoadState.LOADING;

            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            quadtree.update(scene.frameState);

            scene.renderForSpecs();

            // Now there should only be one left in the update queue
            expect(progressEventSpy.calls.mostRecent().args[0]).toEqual(1);

            // Simulate the second zero-level child having loaded with two children.
            quadtree._levelZeroTiles[1].state = QuadtreeTileLoadState.DONE;
            quadtree._levelZeroTiles[1].renderable = true;

            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            quadtree.update(scene.frameState);

            scene.renderForSpecs();

            // Now that tile's four children should be in the load queue.
            expect(progressEventSpy.calls.mostRecent().args[0]).toEqual(4);
        });

        it('forEachLoadedTile does not enumerate tiles in the START state', function() {
            var tileProvider = createSpyTileProvider();
            tileProvider.getReady.and.returnValue(true);
            tileProvider.computeTileVisibility.and.returnValue(Visibility.FULL);
            tileProvider.computeDistanceToTile.and.returnValue(1e-15);

            // Load the root tiles.
            tileProvider.loadTile.and.callFake(function(frameState, tile) {
                tile.state = QuadtreeTileLoadState.DONE;
                tile.renderable = true;
            });

            var quadtree = new QuadtreePrimitive({
                tileProvider : tileProvider
            });

            // determine what tiles to load
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // load tiles
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // Don't load further tiles.
            tileProvider.loadTile.and.callFake(function(frameState, tile) {
                tile.state = QuadtreeTileLoadState.START;
            });

            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            quadtree.forEachLoadedTile(function(tile) {
                expect(tile.state).not.toBe(QuadtreeTileLoadState.START);
            });
        });

        it('add and remove callbacks to tiles', function() {
            var tileProvider = createSpyTileProvider();
            tileProvider.getReady.and.returnValue(true);
            tileProvider.computeTileVisibility.and.returnValue(Visibility.FULL);
            tileProvider.computeDistanceToTile.and.returnValue(1e-15);

            // Load the root tiles.
            tileProvider.loadTile.and.callFake(function(frameState, tile) {
                tile.state = QuadtreeTileLoadState.DONE;
                tile.renderable = true;
                tile.data = {
                    pick : function() {
                        return undefined;
                    }
                };
            });

            var quadtree = new QuadtreePrimitive({
                tileProvider : tileProvider
            });

            var removeFunc = quadtree.updateHeight(Cartographic.fromDegrees(-72.0, 40.0), function(position) {
            });

            // determine what tiles to load
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            ++scene.frameState.frameNumber;

            // load tiles
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            var addedCallback = false;
            quadtree.forEachLoadedTile(function(tile) {
                addedCallback = addedCallback || tile.customData.length > 0;
            });

            expect(addedCallback).toEqual(true);

            removeFunc();

            ++scene.frameState.frameNumber;

            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            var removedCallback = true;
            quadtree.forEachLoadedTile(function(tile) {
                removedCallback = removedCallback && tile.customData.length === 0;
            });

            expect(removedCallback).toEqual(true);
        });

        it('updates heights', function() {
            var tileProvider = createSpyTileProvider();
            tileProvider.getReady.and.returnValue(true);
            tileProvider.computeTileVisibility.and.returnValue(Visibility.FULL);
            tileProvider.computeDistanceToTile.and.returnValue(1e-15);

            tileProvider.terrainProvider = {
                getTileDataAvailable : function() {
                    return true;
                }
            };

            var position = Cartesian3.clone(Cartesian3.ZERO);
            var updatedPosition = Cartesian3.clone(Cartesian3.UNIT_X);
            var currentPosition = position;

            // Load the root tiles.
            tileProvider.loadTile.and.callFake(function(frameState, tile) {
                tile.state = QuadtreeTileLoadState.DONE;
                tile.renderable = true;
                tile.data = {
                    pick : function() {
                        return currentPosition;
                    },
                    mesh: {}
                };
            });

            var quadtree = new QuadtreePrimitive({
                tileProvider : tileProvider
            });

            quadtree.updateHeight(Cartographic.fromDegrees(-72.0, 40.0), function(p) {
                Cartesian3.clone(p, position);
            });

            // determine what tiles to load
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // load tiles
            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            expect(position).toEqual(Cartesian3.ZERO);

            currentPosition = updatedPosition;

            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            expect(position).toEqual(updatedPosition);
        });

        it('gives correct priority to tile loads', function() {
            var tileProvider = createSpyTileProvider();
            tileProvider.getReady.and.returnValue(true);
            tileProvider.computeTileVisibility.and.returnValue(Visibility.FULL);

            var quadtree = new QuadtreePrimitive({
                tileProvider : tileProvider
            });

            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // The root tiles should be in the high priority load queue
            expect(quadtree._tileLoadQueueHigh.length).toBe(2);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[0]);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[1]);
            expect(quadtree._tileLoadQueueMedium.length).toBe(0);
            expect(quadtree._tileLoadQueueLow.length).toBe(0);

            // Mark the first root tile renderable (but not done loading)
            quadtree._levelZeroTiles[0].renderable = true;

            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // That root tile should now load with low priority while its children should load with high.
            expect(quadtree._tileLoadQueueHigh.length).toBe(5);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[1]);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[0].children[0]);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[0].children[1]);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[0].children[2]);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[0].children[3]);
            expect(quadtree._tileLoadQueueMedium.length).toBe(0);
            expect(quadtree._tileLoadQueueLow.length).toBe(1);
            expect(quadtree._tileLoadQueueLow).toContain(quadtree._levelZeroTiles[0]);

            // Mark the children of that root tile renderable too, so we can refine it
            quadtree._levelZeroTiles[0].children[0].renderable = true;
            quadtree._levelZeroTiles[0].children[1].renderable = true;
            quadtree._levelZeroTiles[0].children[2].renderable = true;
            quadtree._levelZeroTiles[0].children[3].renderable = true;

            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            expect(quadtree._tileLoadQueueHigh.length).toBe(17); // levelZeroTiles[1] plus levelZeroTiles[0]'s 16 grandchildren
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[1]);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[0].children[0].children[0]);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[0].children[0].children[1]);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[0].children[0].children[2]);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[0].children[0].children[3]);
            expect(quadtree._tileLoadQueueMedium.length).toBe(0);
            expect(quadtree._tileLoadQueueLow.length).toBe(5);
            expect(quadtree._tileLoadQueueLow).toContain(quadtree._levelZeroTiles[0]);
            expect(quadtree._tileLoadQueueLow).toContain(quadtree._levelZeroTiles[0].children[0]);
            expect(quadtree._tileLoadQueueLow).toContain(quadtree._levelZeroTiles[0].children[1]);
            expect(quadtree._tileLoadQueueLow).toContain(quadtree._levelZeroTiles[0].children[2]);
            expect(quadtree._tileLoadQueueLow).toContain(quadtree._levelZeroTiles[0].children[3]);

            // Mark the children of levelZeroTiles[0] upsampled
            quadtree._levelZeroTiles[0].children[0].upsampledFromParent = true;
            quadtree._levelZeroTiles[0].children[1].upsampledFromParent = true;
            quadtree._levelZeroTiles[0].children[2].upsampledFromParent = true;
            quadtree._levelZeroTiles[0].children[3].upsampledFromParent = true;

            quadtree.update(scene.frameState);
            quadtree.beginFrame(scene.frameState);
            quadtree.render(scene.frameState);
            quadtree.endFrame(scene.frameState);

            // levelZeroTiles[0] should move to medium priority.
            expect(quadtree._tileLoadQueueHigh.length).toBe(1);
            expect(quadtree._tileLoadQueueHigh).toContain(quadtree._levelZeroTiles[1]);
            expect(quadtree._tileLoadQueueMedium.length).toBe(1);
            expect(quadtree._tileLoadQueueMedium).toContain(quadtree._levelZeroTiles[0]);
            expect(quadtree._tileLoadQueueLow.length).toBe(0);
        });

        it('renders tiles in approximate near-to-far order', function() {
            var tileProvider = createSpyTileProvider();
            tileProvider.getReady.and.returnValue(true);
            tileProvider.computeTileVisibility.and.returnValue(Visibility.FULL);

            var quadtree = new QuadtreePrimitive({
                tileProvider : tileProvider
            });

            tileProvider.loadTile.and.callFake(function(frameState, tile) {
                if (tile.level <= 1) {
                    tile.state = QuadtreeTileLoadState.DONE;
                    tile.renderable = true;
                }
            });

            scene.camera.setView({
                destination : Cartesian3.fromDegrees(1.0, 1.0, 15000.0)
            });
            scene.camera.update(scene.mode);

            return pollToPromise(function() {
                quadtree.update(scene.frameState);
                quadtree.beginFrame(scene.frameState);
                quadtree.render(scene.frameState);
                quadtree.endFrame(scene.frameState);

                return quadtree._tilesToRender.filter(function(tile) { return tile.level === 1; }).length === 8;
            }).then(function() {
                quadtree.update(scene.frameState);
                quadtree.beginFrame(scene.frameState);
                quadtree.render(scene.frameState);
                quadtree.endFrame(scene.frameState);

                // Rendered tiles:
                // +----+----+----+----+
                // |w.nw|w.ne|e.nw|e.ne|
                // +----+----+----+----+
                // |w.sw|w.se|e.sw|e.se|
                // +----+----+----+----+
                // camera is located in e.nw (east.northwestChild)

                var west = quadtree._levelZeroTiles.filter(function(tile) { return tile.x === 0; })[0];
                var east = quadtree._levelZeroTiles.filter(function(tile) { return tile.x === 1; })[0];
                expect(quadtree._tilesToRender[0]).toBe(east.northwestChild);
                expect(quadtree._tilesToRender[1] === east.southwestChild || quadtree._tilesToRender[1] === east.northeastChild).toBe(true);
                expect(quadtree._tilesToRender[2] === east.southwestChild || quadtree._tilesToRender[2] === east.northeastChild).toBe(true);
                expect(quadtree._tilesToRender[3]).toBe(east.southeastChild);
                expect(quadtree._tilesToRender[4]).toBe(west.northeastChild);
                expect(quadtree._tilesToRender[5] === west.northwestChild || quadtree._tilesToRender[5] === west.southeastChild).toBe(true);
                expect(quadtree._tilesToRender[6] === west.northwestChild || quadtree._tilesToRender[6] === west.southeastChild).toBe(true);
                expect(quadtree._tilesToRender[7]).toBe(west.southwestChild);
            });
        });
    }, 'WebGL');

    // Sets the camera to look at a given cartographic position from a distance
    // that will produce a screen-space error at that position that will refine to
    // a given tile level and no further.
    function setCameraPosition(quadtree, frameState, position, level) {
        var camera = frameState.camera;
        var geometricError = quadtree.tileProvider.getLevelMaximumGeometricError(level);
        var sse = quadtree.maximumScreenSpaceError * 0.8;
        var sseDenominator = camera.frustum.sseDenominator;
        var height = frameState.context.drawingBufferHeight;

        var distance = (geometricError * height) / (sse * sseDenominator);
        var cartesian = Ellipsoid.WGS84.cartographicToCartesian(position);
        camera.lookAt(cartesian, new Cartesian3(0.0, 0.0, distance));
    }
});
